package graph;
import unionFindSet.UnionFindSet;

import java.util.*;

//邻接矩阵
public class GraphByMatrix {
    public char[] chars;
    public int[][] matrix;
    public boolean isDirect;//true:有向图   false:无向图

    public GraphByMatrix(int size, boolean isDirect) {
        this.chars = new char[size];
        this.matrix = new int[size][size];
        this.isDirect = isDirect;
        for (int i = 0; i < size; i++) {
            Arrays.fill(matrix[i], Consent.MAX);
        }
    }

    public void initArrayV(char[] array) {
        int n = array.length;
        for (int i = 0; i < n; i++) {
            chars[i] = array[i];
        }
    }

    public boolean addEdge(char source, char dest, int weight) {
        int destIndex = getIndex(dest);
        int sourceIndex = getIndex(source);
        if (destIndex == -1 || sourceIndex == -1) {
            return false;//说明没有这个字符
        }
        matrix[sourceIndex][destIndex] = weight;
        if (!isDirect) matrix[destIndex][sourceIndex] = weight;
        return true;
    }

    private int getIndex(char c) {
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == c) {
                return i;
            }
        }
        return -1;
    }

    public int getDevOfV(char c) {
        int count = 0;
        int index = getIndex(c);
        //统计出度
        for (int j = 0; j < matrix[index].length; j++) {
            if (matrix[index][j] == 1) count++;
        }
        //统计入度
        if (isDirect) {
            for (int i = 0; i < matrix.length; i++) {
                if (matrix[i][index] == 1) count++;
            }
        }
        return count;
    }

    public void printGraph() {
        for (int i = 0; i < chars.length; i++) {
            System.out.print(chars[i] + " ");
        }
        System.out.println();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] != Consent.MAX) {
                    System.out.print(matrix[i][j] + " ");
                } else {
                    System.out.print("♾ ");
                }
            }
            System.out.println();
        }
    }

    //bfs : 宽度优先遍历
    public void bfs(char c) {//c:表示给定起始位置
        int source = getIndex(c);
        if (source == -1) return;
        Queue<Integer> qu = new LinkedList<>();
        boolean[] vis = new boolean[chars.length];
        qu.add(source);
        vis[source] = true;
        while (!qu.isEmpty()) {
            int size = qu.size();
            while (size > 0) {
                Integer i = qu.poll();
                System.out.print(chars[i] + " -> ");
                for (int j = 0; j < matrix[i].length; j++) {
                    if (matrix[i][j] != Consent.MAX && !vis[j]) {
                        qu.add(j);
                        vis[j] = true;
                    }
                }
                size--;
            }
        }
    }

    //dfs : 深度优先遍历
    public void dfs(char c, boolean[] vis) {
        int source = getIndex(c);
        if (source == -1) return;
        System.out.print(chars[source] + " -> ");
        vis[source] = true;
        for (int i = 0; i < matrix[source].length; i++) {
            if (matrix[source][i] != Consent.MAX && !vis[i]) {
                dfs(chars[i], vis);
            }
        }
    }

    public void printGraphKruskal() {
        for (int i = 0; i < matrix.length; i++) {
            System.out.print(chars[i] + " -> ");
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] != Consent.MAX)
                    System.out.print(chars[j] + ":" + matrix[i][j] + " -> ");
            }
            System.out.println();
        }
    }

    class Edge {
        int source;
        int dest;
        int weight;

        public Edge(int source, int dest, int weight) {
            this.source = source;
            this.dest = dest;
            this.weight = weight;
        }
    }

    public int kruskal(GraphByMatrix minTree) {
        //1.初始化数据
        PriorityQueue<Edge> queue = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                queue.add(new Edge(i, j, matrix[i][j]));
            }
        }
        UnionFindSet ufs = new UnionFindSet(n);
        int size = 0;
        int weightSum = 0;
        while (size < n && !queue.isEmpty()) {
            Edge minE = queue.poll();
            int source = minE.source;
            int dest = minE.dest;
            if (ufs.isSameSet(source, dest)) {
                //说明在同一个集合中，则这个边不能添加到minTree中，否者会构成环
            } else {
                ufs.union(source, dest);
                minTree.addEdge(chars[source], chars[dest], minE.weight);
                weightSum += minE.weight;
            }
        }
        return weightSum;
    }

    public int prim(GraphByMatrix minTree, char start) {
        //1.初始化数据
        PriorityQueue<Edge> queue = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });
        int n = matrix.length;
        Set<Integer> setX = new HashSet<>();
        Set<Integer> setY = new HashSet<>();
        int startSource = getIndex(start);
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != start) {
                setY.add(i);
            }
        }
        setX.add(startSource);
        for (int i = 0; i < matrix[startSource].length; i++) {
            if (matrix[startSource][i] != Consent.MAX) {
                queue.add(new Edge(startSource, i, matrix[startSource][i]));
            }
        }
        int size = 1;
        int weightSum = 0;
        while (size <= n && !queue.isEmpty()) {
            Edge tep = queue.poll();
            int source = tep.source;
            int dest = tep.dest;

            if (setX.contains(dest)) continue;

            minTree.addEdge(chars[source], chars[dest], matrix[source][dest]);
            System.out.println(chars[dest]);
            setX.add(dest);
            setY.remove(dest);
            size++;
            weightSum += matrix[source][dest];
            for (int i = 0; i < matrix[dest].length; i++) {
                if (matrix[dest][i] != Consent.MAX && !setX.contains(i)) {
                    queue.add(new Edge(dest, i, matrix[dest][i]));
                }
            }
        }

        return weightSum;
    }

    public void dijkstra(char vSrc, int[] dist, int[] pPath) {
        int n = dist.length;
        int source = getIndex(vSrc);
        boolean[] s = new boolean[n];
        Arrays.fill(dist, Consent.MAX);
        dist[source] = 0;
        Arrays.fill(pPath, -1);
        pPath[source] = source;

        for (int i = 0; i < n; i++) {
            int sIndex = find(dist, s);
            s[sIndex] = true;
            for (int j = 0; j < n; j++) {
                if (matrix[sIndex][j] != Consent.MAX && dist[sIndex] + matrix[sIndex][j] < dist[j] && !s[j]) {
                    dist[j] = dist[sIndex] + matrix[sIndex][j];
                    pPath[j] = sIndex;
                }
            }
        }
    }

    private int find(int[] dist, boolean[] s) {
        int retIndex = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < dist.length; i++) {
            if (!s[i] && dist[i] < min) {
                retIndex = i;
                min = dist[i];
            }
        }
        return retIndex;
    }

    public void printShortPath(char s, int[] dist, int[] parentPath) {
        int sourceIndex = getIndex(s);
        for (int i = 0; i < parentPath.length; i++) {
            if (i != sourceIndex) {
                ArrayList<Integer> list = new ArrayList<>();
                int index = i;
                while (index != sourceIndex) {
                    list.add(index);
                    index = parentPath[index];
                }
                list.add(sourceIndex);
                Collections.reverse(list);
                for (int j = 0; j < list.size(); j++) {
                    System.out.print(chars[list.get(j)] + " -> ");
                }
                System.out.println("权值" + dist[i]);
            }
        }
    }

    //可以解决有 负权的图
    public boolean bellmanFord(char vSrc, int[] dist, int[] pPath) {
        int n = dist.length;
        int source = getIndex(vSrc);
        Arrays.fill(dist, Consent.MAX);
        Arrays.fill(pPath, -1);
        dist[source] = 0;
        pPath[source] = source;

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i] != Consent.MAX && matrix[i][j] != Consent.MAX && dist[i] + matrix[i][j] < dist[j]) {
                        dist[j] = dist[i] + matrix[i][j];
                        pPath[j] = i;
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] != Consent.MAX && dist[i] + matrix[i][j] < dist[j]) {
                    return false;
                }
            }
        }

        return true;
    }


    public void ﬂoydWarShall(int[][] dist, int[][] pPath) {
        int n = dist.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] != Consent.MAX){
                    dist[i][j] = matrix[i][j];
                    pPath[i][j] = i;
                }else{
                    dist[i][j] = Consent.MAX;
                    pPath[i][j] = -1;
                }
                if(i == j){
                    dist[i][j] = 0;
                    pPath[i][j] = i;
                }
            }
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != Consent.MAX && dist[k][j] != Consent.MAX && dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        pPath[i][j] = pPath[k][j];
                    }
                }
            }
        }

    }
}